【题解】 [HNOI2011]卡农 组合数学+DP luoguP3214 | Qiuly's blog!

【题解】 [HNOI2011]卡农 组合数学+DP luoguP3214

Posted on | In | Comments:

什么同种音乐简直是个逗比，最后直接除上 $m!$ 即可。

现在我们需要算出选出 $m$ 的片段的方案数，考虑 $\rm{DP}$ ，设 $dp_i$ 表示前 $i​$ 个片段已经确定，且满足下列要求：

  • 这 $i$ 个片段中没有空集
  • 这 $i$ 个片段互不相同
  • 这 $i$ 个片段中所有的音符的出现次数全部都要是偶数次

现在考虑如何从 $dp_{i-1}$ 转移到 $dp_i$ 。

首先看第三个要求，不难发现在知道前 $i-1$ 个片段的情况下，$i$ 的音符集合一定是确定的—— $i$ 的音符集合一定是前 $i-1$ 个片段中出现次数为奇数的音符。也就是说 $i$ 的集合是随着前 $i-1$ 个片段变换的，已知选择前 $i-1$ 个片段的方案数为 $A_{2^n-1}^{i-1}$ ，那么 $i$ 的方案数也自然是 $A_{2^n-1}^{i-1}$ 。(注意该统计方案保证前 $i-1$ 个片段互不相同)

但是 $i$ 可能是空集，那么这个方案就不成立，方案不成立的个数当然是前 $i-1$ 个片段自由搭配且合法的情况数，那么自然就是 $dp_{i-1}$ ，为什么要计算和法的呢，因为首先计算了的方案数显然是满足第三个要求的，也就是说我们要去掉的也只能是满足第三个要求的不合法方案数，那么自然就是 $dp_{i-1}$ 个了。

最后考虑不满足第二种情况的方案数，首先我们令一个片段 $j$ 和 $i$ 一样(在前 $i-1$ 个片段中最多一个和 $i$ 一样)，这个那么这样子我们将这两个片段都去掉的时候全局的方案数就是 $dp_{i-2}$ 了，因为剩下的一定是合法的。显然 $j$ 可以是前 $i-1$ 个片段中的任意一个，并且重复的音乐集的种类数为 $2^n-1-(i-2)$ ，为什么这么说呢，显然 $2^n-1$ 是非空集的音乐集方案数，$i-2$ 就是说剩下的 $i-2$ 个片段不重复，并且 $i,j$ 也不能与之重复，那么可供 $i,j$ 选择的就剩下 $2^n-1-(i-2)$ 个音乐集了。

也就是说，我们用 $A_{2^n-1}^{i-1}$ 减去这些不合法的方案后剩下的就是 $dp_i$ 了：

最后的答案就是 $dp_m$ 。

关于初始化的问题，首先 $dp_0=0$ ，那么选一个片段呢可以吗？其实不行，因为音符没有重复偶数次，所以一定是全都不合法的，又不允许空集的存在，也就是说 $dp_1=0$ 。用上面的式子从 $dp_2$ 推起即可。

Code：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <cstdio>
using namespace std;
typedef long long ll;

const int N=1e6+2;
#define p 100000007

int n,m;
ll dp[N],A[N];

inline ll pow(ll x,ll y,ll res=1) {
    for(;y;y>>=1,x=x*x%p) if(y&1) res=res*x%p;
    return res%p;
}

int main() {
    scanf("%d%d",&n,&m);
    ll mul=pow(2,n)-1;mul=(mul%p+p)%p;
    A[0]=1;
    for(int i=1;i<=m;++i)
        A[i]=1ll*A[i-1]*(mul-i+1)%p;
    dp[0]=1,dp[1]=0;
    for(int i=2;i<=m;++i) {
        dp[i]=A[i-1]%p;
        dp[i]=(dp[i]-dp[i-1]+p)%p;
        dp[i]=(dp[i]-1ll*dp[i-2]*(i-1)%p*(mul-(i-2))%p+p)%p;
        dp[i]=(dp[i]%p+p)%p;
    }
    ll fac=1;
    for(int i=2;i<=m;++i) fac=1ll*fac*i%p;
    ll inv=pow(fac,p-2);
    printf("%lld\n",dp[m]*inv%p);
    return 0;
}

本文标题:【题解】 [HNOI2011]卡农 组合数学+DP luoguP3214

文章作者:Qiuly

发布时间:2019年05月22日 - 00:00

最后更新:2019年05月22日 - 13:17

原始链接:http://qiulyblog.github.io/2019/05/22/[题解]luoguP3214/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。